<h2>Problem 209</h2>
<div style="color:#666;font-size:80%;">19 September 2008</div><br />
<div class="problem_content">
<p>A <var>k</var>-input <i>binary truth table</i> is a map from <var>k</var> input bits
(binary digits, 0 [false] or 1 [true]) to 1 output bit. For example, the 2-input binary truth tables for the logical AND and XOR functions are:</p>
<div style="text-align:center; margin-left:150px; margin-right:150px;">
<table cellspacing="0" cellpadding="2" border="1" align="left">
<tr style="background-color:#c1daf9;">
<td width="30" align="center"><var>x</var></td>
<td width="30" align="center"><var>y</var></td>
<td><var>x</var> AND <var>y</var></td></tr>
<tr><td align="center">0</td><td align="center">0</td><td align="center">0</td></tr>
<tr><td align="center">0</td><td align="center">1</td><td align="center">0</td></tr>
<tr><td align="center">1</td><td align="center">0</td><td align="center">0</td></tr>
<tr><td align="center">1</td><td align="center">1</td><td align="center">1</td></tr>
</table>
<table cellspacing="0" cellpadding="2" border="1" align="right">
<tr style="background-color:#c1daf9;">
<td width="30" align="center"><var>x</var></td>
<td width="30" align="center"><var>y</var></td>
<td><var>x</var> XOR <var>y</var></td></tr>
<tr><td align="center">0</td><td align="center">0</td><td align="center">0</td></tr>
<tr><td align="center">0</td><td align="center">1</td><td align="center">1</td></tr>
<tr><td align="center">1</td><td align="center">0</td><td align="center">1</td></tr>
<tr><td align="center">1</td><td align="center">1</td><td align="center">0</td></tr>
</table>
</div><br clear="all" />
<p>How many 6-input binary truth tables, &tau;, satisfy the formula</p>
<div style="text-align:center;">
&tau;(<var>a</var>, <var>b</var>, <var>c</var>, <var>d</var>, <var>e</var>, <var>f</var>) AND &tau;(<var>b</var>, <var>c</var>, <var>d</var>, <var>e</var>, <var>f</var>, <var>a</var> XOR (<var>b</var> AND <var>c</var>)) = 0
</div><br />
<p>for all 6-bit inputs (<var>a</var>, <var>b</var>, <var>c</var>, <var>d</var>, <var>e</var>, <var>f</var>)?
</p>
</div><br />
